<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 回溯算法就是纯暴力穷举，复杂度一般都很高。
      // 代码框架
      // result = []
      // backtrack(路径, 选择列表):
      // if 满足结束条件:
      //   result.add(路径)
      //   return

      // for 选择 in 选择列表:
      //   做选择
      //   backtrack(路径, 选择列表)
      //   撤销选择
      // 全排列 问题  构建决策树

      function permute(nums) {
        var res = [];
        var track = [];
        backtrack(nums, track);
        return res;

        // nums 选择列表
        // 路径列表
        function backtrack(nums, track) {
          // 结束条件
          if (track.length == nums.length) {
            res.push(track.slice(0));
            return;
          }
          for (var i = 0; i < nums.length; i++) {
            if (track.includes(nums[i])) {
              continue;
            }
            // 做选择
            track.push(nums[i]);
            backtrack(nums, track);
            // 撤销选择
            track.pop();
          }
        }
      }
      console.log(permute([1, 2, 3]));

      // N皇后问题
      // 这个问题很经典了，简单解释一下：给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。

      // PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
    </script>
  </body>
</html>
